#include <iostream>
#include <climits>
#include <string.h>
#include <vector>
#include <fstream>

#include <LEDA/graphics/graphwin.h>
#include <LEDA/graphics/color.h>
#include <LEDA/system/basic.h>
#include "control.h"

#include <LEDA/core/partition.h>
#include <LEDA/core/p_queue.h>
#include <LEDA/graph/node_partition.h>
#include <LEDA/graph/node_array.h>
#include <LEDA/graph/graph_iterator.h>




using namespace leda;

/**
 * Get edge weight of a given edge e
 */
double get_edge_weight(GraphWin & gw , edge e)
{
	string edge_label = gw.get_user_label(e);
	double weight = atof(edge_label.c_str());
	return weight;
}

/**
 * Dijkstra's algorithm to compute shortest paths in a directed graph.
 */
void dijkstra(graph &g, GraphWin &gw)
{
	// set the start node
	node start = g.first_node();
	//gw.set_color(start , green);
	// set the end node
	node end = g.last_node();
	//gw.set_color(end , red);

	// unknown distance from source to v (initialized to infinity)
	node_array<double> dist(g,INFINITY);
	// previous node in optimal path from source
	node_array<node> from(g,NULL);
	// mark edge that belong to the path
	edge_array<bool> edge_marker(g, false);

	// distance from source to source
	dist[start] = 0.0;
	// set label with distance
	gw.set_label(start , string("%g" , dist[start]));
	//store all pq_items for quick access for updates etc.
	node_array<bin_heap_item> node_pq_pointer(g , NULL);

	//marks the presence of a node in the tree
	node_array<bool> marker(g, false);

	//Color the starting node
	//gw.set_color(start , blue);
	//priority queue for all nodes adjacent to our tree
	p_queue<double, edge> priority_queue;

	edge e_iter;

	forall_out_edges(e_iter, start) {
		//insert the edge into the priority queue
		bin_heap_item it = priority_queue.insert(get_edge_weight(gw, e_iter) , e_iter);
		//gw.set_color(e_iter , green);
		//gw.set_color(g.opposite(e_iter , start) , green);
		//control_wait(0.5);
		//save the pq_item in a map for quick access through the target node
		node target = g.opposite(e_iter, start);
		node_pq_pointer[target] = it;
		//node start is the first node in our tree. Therefore we mark it as visited.
		marker[start] = true;
	}
	//pop edges from the priority queue and add them to our tree.
	//after that check all its neighbors and update the priority queue

	while(!priority_queue.empty())
	{
		edge e = priority_queue.inf(priority_queue.find_min());
		double path_length = priority_queue.prio(priority_queue.find_min());

		// delete item from priority queue
		priority_queue.del_min();

		//see which side of the edge is not yet marked
		node target = g.opposite(target, e);
		if (marker[target])
		{
			target = g.opposite(target, e);
		}

		//add edge to shortest path tree
		//control_wait(0.5);
		//		gw.set_color(e, red);
		//		gw.set_width(e, 3);
		edge_marker[e] = true;
		//gw.set_color(target, blue);
		//gw.set_color(g.opposite(target, e), blue);
		gw.set_label(target , string("%g" , path_length));
		//control_wait(0.1);

		// mark target as visited
		marker[target] = true;

		dist[target] = path_length;
		from[target] = g.opposite(e , target);

		// unset the pointer from target to its pq_item (it is gone anyway)
		node_pq_pointer[target] = NULL;

		// now we need to update the priority queue with the neighbors of target
		edge adj_edge;

		forall_out_edges(adj_edge, target)
		{
			node neighbour = g.opposite(adj_edge, target);

			// ignore self-loops and nodes that are marked
			if ((neighbour != target) && (!marker[neighbour]))
			{
				// get the priority queue item.
				bin_heap_item node_item = node_pq_pointer[neighbour];

				double new_distance = dist[target] + get_edge_weight(gw , adj_edge);
				// if item exists check if we have to update it
				// else we add a new item to the list
				if (node_item != NULL)
				{
					if (priority_queue.prio(node_item) > new_distance)
					{
						// replace the current edge with the 'better' edge
						priority_queue.change_inf(node_item, adj_edge);
						priority_queue.decrease_p(node_item, new_distance);

						edge neighbor_edges;
						forall_inout_edges(neighbor_edges , neighbour) {
							//gw.set_color(neighbor_edges , grey3);
						}
						//gw.set_color(adj_edge , green);
						//gw.set_color(neighbour , green); //not really needed, just making sure it is green..
					}
				}
				else
				{
					// if the node is not yet in our queue we add it
					// and add the reference in the node_pq_pointer map
					bin_heap_item new_item = priority_queue.insert(new_distance, adj_edge);

					node_pq_pointer[neighbour] = new_item;

					// finally we color it to indicate that this is a adjacent edge
					// which will be considered in the next round
					//gw.set_color(adj_edge , green);
					//gw.set_color(neighbour , green);
					//control_wait(0.5);
				}

			} // end if (neighbor != target && !marker[neighbor])

		} // end forall_inout_edges

	} // end while

	// color path;
	node curr_node = end;
	gw.set_color(end , blue);
	do{
		edge e;
		forall_in_edges(e, curr_node){
			node neighbour = g.opposite(e, curr_node);
			if (edge_marker[e] == true){
				gw.set_color(e, blue);
				gw.set_color(neighbour , blue);
				curr_node = neighbour;
			}
		}
	}
	while (curr_node != start);
}


//CHeck if a=b, if so return 0, else return 1
int delta(char a , char b) {
	if (a == b)
		return 0;

	return 1;
}


// Compute the edit distance between x and y using Dynamic Programming
int DPeditDistance(char * x , char * y) {

	//Get size of input
	int m = strlen(x);
	int n = strlen(y);

	//Get matrix size , number of iterations (=rows / columns)
	int length = n+1;
	int iterations = m;

	//Check which way we go (left to right or top to bottom)
	if (m < n) {
		length = m+1;
		iterations = n;
		//Also swap x and y!
		char * swap = x;
		x = y;
		y = swap;
	}

	//init 2 rows of matrix (more will not be needed)
	int * row1 = new int[length];
	int * row2 = new int[length];

	//initialize first row (or column if not horizontal)
	for (int i=0; i<length;i++) {
		row1[i] = i;
		//std::cout << string("%i ",row1[i]);
	}
	//std::cout << std::endl;

	int j = 1; // This will be increased until row n (or column m) is done

	while (j <= iterations) {

		for (int i=0; i<length;i++) {
			//If we are on the left ( or top ) border, the value is already clear
			if (i == 0)
				row2[i] = j;
			else {
				row2[i] = std::min(row1[i]+1 , std::min(row2[i-1]+1 , row1[i-1] + delta(x[j-1] , y[i -1])));
			}

			//std::cout << string("%i " , row2[i]);
		}
		//std::cout << std::endl;
		j++;

		//row 2 is now complete, so we will never need row 1 again. Therefore row 2 is the new
		//row 1 and row 1 will be reused as next row 2

		row1 = row2;
		row2 = new int[length];

	}
	//row1 is now the last line of the distance matrix. Return last element of it.
	return row1[length-1];

}

// Compute the edit distance between x and y using graph algorithms
void graphEditDistance(GraphWin &gw , char * x , char * y) {

	gw.message("Setting up nodes and labels in graph!");

	int m = strlen(x);
	int n = strlen(y);

	// create node_matrix [0..n][0..m] aka [line][column]
	std::vector<std::vector<node> > node_matrix;

	// unit distance between nodes
	int x_unit = ( gw.get_xmax() - gw.get_xmin() ) / (m+2);
	int y_unit = ( gw.get_ymax() - gw.get_ymin() ) / (n+2);

	// Create nodes
	for (int j = 0 ; j <= n; j++) { // columns

		//push an empty line in the matrix
		node_matrix.push_back(std::vector<node>());

		for (int i = 0 ; i <= m; i++) { // lines

			// set node deployment position
			point p = point(x_unit * (i+1), gw.get_ymax() - (y_unit * (j+1)));
			node curr_n = gw.new_node(p);

			// set labels
			if (j==0 && i!=0){//first line, write X characters
				gw.set_label(curr_n , string("%c",x[i-1]));
			}
			else if (i==0 && j!=0){//first column, write Y characters
				gw.set_label(curr_n , string("%c",y[j-1]));
			}
			else/*(i!=0 || j!=0)*/{
				//gw.set_label(curr_n , string("%i,%i", j, i));
				gw.set_label(curr_n ,"");
			}
			//gw.update_graph();

			// push node into the current line
			node_matrix[j].push_back(curr_n);
		}
	}

	// Create edges
	for (int j = 0 ; j <= n; j++) { // columns
		for (int i = 0 ; i <= m; i++) {// lines

			//horizontal edge
			if (i!=m){
				edge he = gw.new_edge(node_matrix[j][i],node_matrix[j][i+1]);
				gw.set_label(he , "1");
			}
			//vertical edge
			if (j!=n){
				edge ve = gw.new_edge(node_matrix[j][i],node_matrix[j+1][i]);
				gw.set_label(ve , "1");
			}

			//diagonal edge
			if (i!=m && j!=n){
				edge de = gw.new_edge(node_matrix[j][i],node_matrix[j+1][i+1]);
				// compare the edge labels, and set coresponding weights
				if (strcmp(gw.get_label(node_matrix[j+1][0]).c_str(), gw.get_label(node_matrix[0][i+1]).c_str()) != 0){
					gw.set_label(de , "1");
				}
				else{
					gw.set_label(de , "0");
				}
			}
		}
	}

	gw.update_graph();
	graph g = gw.get_graph();

	gw.acknowledge("Press continue to start Dijkstra!");
	gw.message("Starting Dijkstra! Distances are node labels!");

	//Run Dijkstra
	dijkstra(g , gw);
}



int main(int argc, char *argv[])
{
	char * x;
	char * y;
	std::string str_x;
	std::string str_y;

	if (argc > 1){
		std::ifstream textfile(argv[1]);

		if (textfile.is_open())
		{

			std::getline(textfile, str_x, '$');
			std::getline(textfile, str_y, '$');
			str_y.erase(0,1); //erase '\n' from string Y
			textfile.close();
		}
		else {
			std::cout << "[Error] Unable to open file "<< argv[1] << std::endl;
			return 0;
		}
	}
	else{
		std::cout << "[Error] Add input file as argument, e.g. './input/textpair1.txt'" << std::endl;
		return 0;
	}

	x = const_cast<char*> (str_x.c_str());
	y = const_cast<char*> (str_y.c_str());

	std::cout << "X=" << x << std::endl;
	std::cout << "Y=" << y << std::endl;


	// Reading the running type
	window *MaxMinWindowP;
	MaxMinWindowP = new leda::window(260, 40, "Running type");
	MaxMinWindowP->buttons_per_line(2);
	MaxMinWindowP->button("Graph",  1);
	MaxMinWindowP->button("Terminal",  2);
	MaxMinWindowP->display(0, 0);
	int running_type = MaxMinWindowP->read_mouse();
	MaxMinWindowP->close();


	if (running_type == 1) {
		GraphWin gw(800, 600);
		gw.display();
		create_control();
		gw.set_directed(true);

		/* run edit distance in graph mode*/
		graphEditDistance(gw , x , y);

		gw.edit();
		gw.close();
		destroy_control();
		exit(0);
	}

	if (running_type == 2) {
		/* run edit distance in terminal mode, and return edit ditance*/
		std::cout << "Edit distance: " << DPeditDistance(x , y) << std::endl;
	}

	return 0;

}
